#include <stdlib.h>

#include <iostream>
using std::cout;
using std::endl;

int compare(const void *pa, const void *pb) {
  int a = *((const int *)pa);
  int b = *((const int *)pb);
  return a - b;
}

// C语言的qsort在数据规模较小时使用归并排序
// 在数据规模大时使用快排，三数取中作为分区点，为防止递归栈溢出在堆上模拟栈
// 快排时数据规模<=4时，使用插入排序
void testCqsort() {
  int arr[] = {4, 2, 5, 1, 9, 7, 5, 3, 8, 8};
  size_t num = sizeof(arr) / sizeof(int);
  qsort(arr, num, sizeof(int), compare);
  for (int i = 0; i < num; ++i) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

int main() { testCqsort(); }